"""
https://leetcode.cn/problems/basic-calculator-ii/description/

227. 基本计算器 II
中等
相关标签
相关企业
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

 

示例 1：

输入：s = "3+2*2"
输出：7
示例 2：

输入：s = " 3/2 "
输出：1
示例 3：

输入：s = " 3+5 / 2 "
输出：5
 

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

"""



from typing import List


class Solution:

    def oper_priority(self, ch):
        if ch=='+' or ch=='-':
            return 1
        elif ch=='*' or ch=='/':
            return 2
        else:
            return 0

    def eval_oper(self,oper_ch:str,num1:int,num2:int)->int:
        if oper_ch=='+':
            return num1+num2
        elif oper_ch=='-':
            return num1-num2
        elif oper_ch=='*':
            return num1*num2
        elif oper_ch=='/':
            return num1//num2

    def calculate(self, s: str) -> int:
        """
        几个要点：
        1. 数字的识别
        2. 运算符号优先级控制（*/优先级高于+-）

        提升空间：
        使用ord计算和isDigits方法，可以优化速度
        """
        num_ch_sta:List[str]=[]
        num_val_sta:List[int]=[]
        oper_sta:List[str]=[]
        for ch in s:
            if ch==' ':
                continue
            if ord('0')<=ord(ch)<=ord('9'):
                num_ch_sta.append(ch)
            else:
                # 数字收集
                if num_ch_sta:
                    num_val_sta.append(int(''.join(num_ch_sta)))
                    num_ch_sta=[]
                # 符号处理
                while oper_sta and self.oper_priority(oper_sta[-1])>=self.oper_priority(ch):
                    old_oper=oper_sta.pop()
                    num2=num_val_sta.pop()
                    num1=num_val_sta.pop()
                    cache_num=self.eval_oper(old_oper,num1,num2)
                    num_val_sta.append(cache_num)
                oper_sta.append(ch)
        
        # 最后处理
        if num_ch_sta:
            num_val_sta.append(int(''.join(num_ch_sta)))
            num_ch_sta=[]

        while oper_sta:
            oper=oper_sta.pop()
            num2=num_val_sta.pop()
            num1=num_val_sta.pop()
            cache_num=self.eval_oper(oper,num1,num2)
            num_val_sta.append(cache_num)

        return num_val_sta[0]
    
if __name__=='__main__':
    sol=Solution()
    s='1*2-3/4+5*6-7*8+9/10'
    result=sol.calculate(s)
    print(result)